package com.josework.springhelloworld.algorithm;

import java.util.Arrays;

/**
 * 选择排序
 * 是冒泡排序的优化。冒泡排序是通过相邻的比较和交换。选择排序是通过整体的选择。
 *
 * 对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.
 * 对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。
 *
 * 选择排序的时间复杂度为O(n^2)
 */
public class SelectSort {

    public static void selectSort(int[] arr){

        if (arr == null || arr.length ==0){
            return;
        }

        for (int i = 0; i< arr.length-2;i++){ //只需要比较n-1次
            int minIndex = i;
            for (int j = i+1; j<arr.length-1;j++){ //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){ //如果minIndex不为i，说明找到了更小的值，交换之。
                swap(arr,i,minIndex);
            }

        }



    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5,3,8,6,9};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }


}
